home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c++-part2 / 14756 < prev    next >
Encoding:
Text File  |  1996-08-05  |  1.5 KB  |  38 lines
  1. Path: news.compuserve.com!newsmaster
  2. From: Philippe Verdy <100105.3120@compuserve.com>
  3. Newsgroups: comp.lang.c++
  4. Subject: Re: merge sort
  5. Date: 2 Apr 1996 00:01:52 GMT
  6. Organization: CompuServe Incorporated
  7. Message-ID: <4jpqpg$lhj@dub-news-svc-6.compuserve.com>
  8. NNTP-Posting-Host: ad15-078.compuserve.com
  9.  
  10. PC Lab User <lab-mail@cs.utas.edu.au> s'Θcrit :
  11. > has anyone got some source for the "merge" algorithm used in mergesort?
  12. > thanx
  13. > 
  14. > m_wookey@postoffice.utas.edu.au
  15. This sort algorithm is of the same general idea as the QuickSort:
  16. Divide and conquer. It is dividing a segment to sort, into two
  17. subsegments to sort.
  18.  
  19. With QuickSort: divide a segment in two parts, one for
  20. the keys below a given key, the other for all the keys
  21. higher than the same key. This key is called the pivot.
  22. The difficulty is to create this partition efficiently,
  23. so that minimum swaps occur. This is harder when you want
  24. this partition to be stable (i.e. keeping the relative
  25. order of equal keys) because it involves sliding groups
  26. of keys during the partition. There is in all cases no
  27. final step after the recursive calls.
  28.  
  29. With merge sort, you don't choose a pivot, but divide the
  30. segment in two arbitrary subsegments, then call merge sort
  31. recursively on each of them.
  32. Once this is done, you have to merge these two segments
  33. The difficulty resides in this merging operation if you
  34. only have one medium to store them: This involves sliding
  35. groups of elements. But in all cases, this sort is stable
  36. and easier to understand.
  37.  
  38.